package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-04-25 20:11
 */
public class QLint143 {
    public void sortColors2(int[] colors, int k) {
        if(colors == null || colors.length == 0) {
            return;
        }

        sort(colors, 0, colors.length - 1, 1, k);
    }

    private void sort(int[] colors, int start, int end, int colorStart, int colorEnd) {
        if(start >= end || colorStart >= colorEnd) {
            return;
        }

        int privo = (colorStart + colorEnd) / 2;
        int i = start, j = end;
        while (i <= j) {
            while (i <= j && colors[i] <= privo) {
                i++;
            }

            while (i <= j && colors[j] > privo) {
                j--;
            }

            if(i <= j) {
                int temp = colors[i];
                colors[i] = colors[j];
                colors[j] = temp;

                i++;
                j--;
            }
        }

        sort(colors, start, j, colorStart, privo);
        sort(colors, i, end, privo + 1, colorEnd);
    }
}
